<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8">
		<meta name="keywords" content="道格拉斯-普克算法">
		<meta name="author" content="南师大地科院10170313">
		<meta name="description" content="2019_GIS算法基础_道格拉斯-普克算法">
		<title>道格拉斯-普克算法</title>
		<style type="text/css">
			.buttons {
				background-color: white;
				border: 2px solid cyan;
				border-radius: 12%;
				width: 70px;
				margin-left: 70px;
			}
			
			.buttons:hover {
				background-color: aquamarine;
				color: white;
				box-shadow: 0 12px 16px 0 rgba(0, 0, 0, 0.24);
			}

			.radios {
				background-color: white;
				margin-left: 70px;
			}
		</style>
	</head>
	<body bgcolor="azure">
		<h1 style="margin: 10px auto; width: 900px; text-align: center; background-color: cyan; font-family: '楷体';">道格拉斯-普克算法数据压缩</h1>
		<p style="margin-right: 20px; float: right; font-style: italic;"><small>By 10170313</small></p>
		<br>
		<div style="width: 1002px; margin: 0 auto;">
			<input id="fileRead" type="file" style="visibility: hidden; position: absolute;" onchange="getPoints()">
			<button type="button" class="buttons" onclick="fileRead.click()">加载</button>
			<p id="compression" style="display: inline; margin-left: 70px;">压缩率： %</p>
			<button type="button" disabled="disabled" class="buttons" name="radios" onclick="getAfterPolygons()">压缩</button>
			<p style="display: inline; margin-left: 70px;">阈值：</p>
			<input id="maxdis" type="text" value="3066" style="width: 70px;" onchange="setTolerance(this.value)">
			<input type="radio" disabled="disabled" class="radios" name="radios" value="before" checked="checked" onclick="setValue(this.value)">压缩前
			<input type="radio" disabled="disabled" class="radios" name="radios" value="after" onclick="setValue(this.value)">压缩后
		</div>
		<div style="width: 802px; margin: 10px auto;">
			<canvas id="map" width="800" height="600" style="background-color: white; border: 1px solid black;"></canvas>
		</div>

		<script type="text/javascript">
			//全局变量的设置
			//地图点
			function mapPoint(x, y) {
				this.x = x;
				this.y = y;
			}
			//暂存点,多了一个del用于标记该点最终是否要删除
			function tempPoint(del, x, y) {
				this.del = del;
				this.x = x;
				this.y = y;
			}
			//面对象,包括了编号和点坐标数组
			function Polygon(number, points) {
				this.number = number;
				this.points = points;
			}

			var polygonsBefore = new Array();//压缩前面的数组
			var polygonsAfter = new Array();//压缩后面的数组
			var change = "before";//压缩前后标识
			var tolerance = document.getElementById('maxdis').value;//阈值
			var lastTolerance = 0;//暂存上一次的阈值

			var canva = document.getElementById('map');
			var cxt = canva.getContext('2d');
			var isDraw = false;
		</script>

		<script type="text/javascript">
			//读取文件,得到压缩前的面
			function getPoints() {
				//重置某些全局变量
				polygonsBefore.splice(0,polygonsBefore.length);
				polygonsAfter.splice(0,polygonsAfter.length);
				lastTolerance=0;
				var file = document.getElementById('fileRead').files[0];
				var reader = new FileReader();
				reader.readAsText(file);
				//读取和存储
				reader.onload = function(e) {
					var str = reader.result;
					var numcharacter = "";
					var x = 0,
						y = 0;
					var flag = 0;
					var number = 0;
					var character = str[flag];
					var pointTemp = new mapPoint(0, 0);
					var pointsTemp = new Array();
					while (character != null) {
						if (character == "E") {
							flag += 5;
							character = str[flag];
						} else {
							while (character != "\n") {
								numcharacter += character;
								character = str[++flag];
							}
							number = parseInt(numcharacter);
							numcharacter = "";
							character = str[++flag];
							while (character != "E") {
								while (character != ",") {
									numcharacter += character;
									character = str[++flag];
								}
								character = str[++flag];
								pointTemp.x = parseFloat(numcharacter);
								numcharacter = "";
								while (character != "\n") {
									numcharacter += character;
									character = str[++flag];
								}
								character = str[++flag];
								pointTemp.y = parseFloat(numcharacter);
								numcharacter = "";
								pointsTemp.push(JSON.parse(JSON.stringify(pointTemp)));
							}
						}
						var points = pointsTemp.slice();
						var polygon = new Polygon(number, points);
						polygonsBefore.push(polygon);
						pointsTemp.splice(0, pointsTemp.length);
						flag += 5;
						character = str[flag];
					}
					polygonsBefore.pop();//消除最后一个END的影响
					draw();//绘制
					//取消某些按钮的禁用
					var obj=document.getElementsByName('radios');
					for(var i=0;i<obj.length;i++){
						obj[i].disabled=false;
					}
				}
			}
			//设置变化标识值
			function setValue(value) {
				change = value;
				draw();
			}
			//设置阈值
			function setTolerance(value) {
				tolerance = value;
			}
			//得到压缩后的点
			function getAfterPolygons() {
				//阈值改变的情况下才重新压缩
				if (lastTolerance != tolerance) {
					//清除上次压缩后的点
					if (polygonsAfter.length != 0) {
						polygonsAfter.splice(0, polygonsAfter.length);
					}
					var N = polygonsBefore.length;
					for (var i = 0; i < N; i++) {
						var n = polygonsBefore[i].points.length;
						if (polygonsBefore[i].points[0].x != polygonsBefore[i].points[n - 1].x||
						(polygonsBefore[i].points[0].x == polygonsBefore[i].points[n - 1].x&&
						polygonsBefore[i].points[0].y != polygonsBefore[i].points[n - 1].y)) {
							//当线段不围成一个面时
							var number = polygonsBefore[i].number;
							var poistemp = new Array();
							var poideltemp = new Array();
							//将转换前的点转为带del标识的点
							for (var j = 0; j < n; j++) {
								var poiWithDel = new tempPoint(false, 0, 0);
								poiWithDel.x = polygonsBefore[i].points[j].x;
								poiWithDel.y = polygonsBefore[i].points[j].y;
								poideltemp.push(JSON.parse(JSON.stringify(poiWithDel)));
							}
							DouglasPeucker(poideltemp, 0, poideltemp.length - 1);//进行道格拉斯压缩
							//保留不被压缩掉的点存入poistemp
							for (var j = 0; j < n; j++) {
								if (poideltemp[j].del == false) {
									var poiSave = new mapPoint(0, 0);
									poiSave.x = poideltemp[j].x;
									poiSave.y = poideltemp[j].y;
									poistemp.push(poiSave);
								}
							}
							var points = poistemp.slice();//转存
							poistemp.slice(0, poistemp.length);
							var polygon = new Polygon(number, points);
							polygonsAfter.push(JSON.parse(JSON.stringify(polygon)));//得到压缩后的一条线段
						} else {
							//当线段围成面时
							var poistemp = new Array();
							var number = polygonsBefore[i].number;
							var cut = getCutNumber(polygonsBefore[i].points);//找到离起点最远点的下标,以此切断面
							//将前半段转存入带del标识的poistemp1
							var poistemp1 = new Array();
							for (var j = 0; j < cut; j++) {
								var poiWithDel = new tempPoint(false, 0, 0);
								poiWithDel.x = polygonsBefore[i].points[j].x;
								poiWithDel.y = polygonsBefore[i].points[j].y;
								poistemp1.push(JSON.parse(JSON.stringify(poiWithDel)));
							}
							//将后半段转存入带del标识的poistemp2
							var poistemp2 = new Array();
							for (var j = cut; j < n; j++) {
								var poiWithDel = new tempPoint(false, 0, 0);
								poiWithDel.x = polygonsBefore[i].points[j].x;
								poiWithDel.y = polygonsBefore[i].points[j].y;
								poistemp2.push(JSON.parse(JSON.stringify(poiWithDel)));
							}
							//进行压缩
							DouglasPeucker(poistemp1, 0, poistemp1.length - 1);
							DouglasPeucker(poistemp2, 0, poistemp2.length - 1);
							//得到压缩后剩下的点
							for (var j = 0; j < poistemp1.length; j++) {
								if (poistemp1[j].del == false) {
									var poiSave = new mapPoint(0, 0);
									poiSave.x = poistemp1[j].x;
									poiSave.y = poistemp1[j].y;
									poistemp.push(JSON.parse(JSON.stringify(poiSave)));
								}
							}
							for (var j = 0; j < poistemp2.length; j++) {
								if (poistemp2[j].del == false) {
									var poiSave = new mapPoint(0, 0);
									poiSave.x = poistemp2[j].x;
									poiSave.y = poistemp2[j].y;
									poistemp.push(JSON.parse(JSON.stringify(poiSave)));
								}
							}
							//得到压缩后的一段线段
							var points = poistemp.slice();
							poistemp.splice(0, poistemp.length);
							var polygon = new Polygon(number, points);
							polygonsAfter.push(polygon);
						}
					}
					lastTolerance = tolerance;//将这次的阈值暂存
					setCompressionRatio();//计算压缩率
					draw();//绘制
				}
			}
			//绘制地图
			function draw() {
				if (isDraw == true) {
					cxt.clearRect(0, 0, canva.width, canva.height);
				}
				//绘制未压缩的地图
				if (change == "before") {
					var N = polygonsBefore.length;
					//带有缩放和平移信息的对象
					var vary={
						scale:0,//缩放比例
						moveX:0,//X轴移动长度
						moveY:0//Y轴移动长度
					}
					getVary(polygonsBefore,vary);//得到缩放和平移的信息
					//绘制
					for (var i = 0; i < N; i++) {
						var n = polygonsBefore[i].points.length;
						cxt.beginPath();
						var xt=(polygonsBefore[i].points[0].x+vary.moveX) * vary.scale;
						var yt=canva.height - (polygonsBefore[i].points[0].y+vary.moveY)*vary.scale;
						cxt.moveTo(xt, yt);
						for (var j = 1; j < n; j++) {
							var xt=(polygonsBefore[i].points[j].x+vary.moveX) * vary.scale;
							var yt=canva.height - (polygonsBefore[i].points[j].y+vary.moveY)*vary.scale;
							cxt.lineTo(xt, yt);
						}
						cxt.stroke();
						cxt.beginPath();
					}
				}
				//绘制压缩后的地图
				if (change == "after") {
					var N = polygonsAfter.length;
					var vary={
						scale:0,//缩放比例
						moveX:0,//X轴移动长度
						moveY:0//Y轴移动长度
					}
					getVary(polygonsAfter,vary);
					for (var i = 0; i < N; i++) {
						var n = polygonsAfter[i].points.length;
						cxt.beginPath();
						var xt=(polygonsAfter[i].points[0].x+vary.moveX) * vary.scale;
						var yt=canva.height - (polygonsAfter[i].points[0].y+vary.moveY)*vary.scale;
						cxt.moveTo(xt, yt);
						for (var j = 1; j < n; j++) {
							var xt=(polygonsAfter[i].points[j].x+vary.moveX) * vary.scale;
							var yt=canva.height - (polygonsAfter[i].points[j].y+vary.moveY)*vary.scale;
							cxt.lineTo(xt, yt);
						}
						cxt.stroke();
						cxt.beginPath();
					}
				}
				isDraw = true;
			}
			//根据传入的地图点确定缩放的比例和平移长度
			function getVary(polygons,vary){
				var N=polygons.length;
				var xMin=polygons[0].points[0].x;
				var yMin=polygons[0].points[0].y;
				var xMax=polygons[0].points[0].x;
				var yMax=polygons[0].points[0].y;
				//获取最小外接矩形
				for(var i=0;i<N;i++){
					var n=polygons[i].points.length;
					for(var j=0;j<n;j++){
						if(polygons[i].points[j].x<xMin){
							xMin=polygons[i].points[j].x;
						}
						if(polygons[i].points[j].x>xMax){
							xMax=polygons[i].points[j].x;
						}
						if(polygons[i].points[j].y<yMin){
							yMin=polygons[i].points[j].y;
						}
						if(polygons[i].points[j].y>yMax){
							yMax=polygons[i].points[j].y;
						}
					}
				}
				//分别计算xy方向的缩放比例
				var scaleX=canva.width/(xMax-xMin);
				var scaleY=canva.height/(yMax-yMin);
				//选取合适的缩放比例,计算平移量
				if(scaleX<scaleY){
					vary.scale=scaleX;
					var dy=(yMax-yMin)*scaleX;
					var upY=(canva.height-dy)/2/scaleX;
					vary.moveX=-xMin;
					vary.moveY=-yMin+upY;
				}else{
					vary.scale=scaleY;
					var dx=(xMax-xMin)*scaleY;
					var upX=(canva.width-dx)/2/scaleY;
					vary.moveX=-xMin+upX;
					vary.moveY=-yMin;
				}
			}
			//获取离起点最远的点的下标
			function getCutNumber(points) {
				var dismax = 0;
				var temp = 0;
				var n = points.length;
				for (var i = 1; i < n; i++) {
					var dx = points[i].x - points[0].x;
					var dy = points[i].y - points[0].y;
					var dis = Math.sqrt(dx * dx + dy * dy);
					if (dis > dismax) {
						dismax = dis;
						temp = i;
					}
				}
				return temp;
			}
			//道格拉斯压缩算法
			function DouglasPeucker(points, start, end) {
				//只剩首尾两个点退出递归
				if (end - start == 1) {
					return 0;
				}
				var distance = 0;
				var temp = 0;
				//获取最大距离
				for (var i = start + 1; i < end - 1; i++) {
					var distemp = distanceToLine(points[start].x, points[start].y, points[end].x, points[end].y, points[i].x, points[i]
						.y);//点到线的距离
					if (distemp > distance) {
						distance = distemp;
						temp = i;
					}
				}
				//最大距离小于阈值则全部舍去
				if (distance <= tolerance) {
					for (var i = start + 1; i < end - 1; i++) {
						points[i].del = true;
					}
					return 0;
				} else {
					//否则进入下一层递归
					DouglasPeucker(points, start, temp);
					DouglasPeucker(points, temp + 1, end);
				}
			}
			//点到直线距离
			function distanceToLine(x1, y1, x2, y2, x0, y0) {
				var A = y2 - y1;
				var B = x1 - x2;
				var C = x2 * y1 - x1 * y2;
				var dis = Math.abs(A * x0 + B * y0 + C) / Math.sqrt(A * A + B * B);
				return dis;
			}
			//计算压缩率并显示
			function setCompressionRatio() {
				var numBefore = 0;
				var numAfter = 0;
				var comp = 0;

				for (var i = 0; i < polygonsBefore.length; i++) {
					numBefore += polygonsBefore[i].points.length;
				}
				for (var i = 0; i < polygonsAfter.length; i++) {
					numAfter += polygonsAfter[i].points.length;
				}
				comp = (numAfter / numBefore * 100).toFixed(2);

				var obj = document.getElementById('compression');
				obj.innerHTML = "压缩率：" + comp.toString() + " %";
			}
		</script>
	</body>
</html>
